/**
 * Bloom Filter (布隆过滤器) 实现
 * 
 * 布隆过滤器是一种空间效率极高的概率型数据结构，用于判断一个元素是否在集合中。
 * 它可能会产生假阳性（false positive），但不会产生假阴性（false negative）。
 * 
 * 时间复杂度：
 * - 插入: O(k) k为哈希函数数量
 * - 查询: O(k)
 * 
 * 空间复杂度: O(m) m为位数组大小
 */

class BloomFilter {
  constructor(expectedItems, falsePositiveRate) {
    // TODO: 初始化布隆过滤器
    // this.expectedItems = expectedItems
    // this.falsePositiveRate = falsePositiveRate
    
    // 计算最优的位数组大小和哈希函数数量
    // this.bitArraySize = Math.ceil(
    //   -(expectedItems * Math.log(falsePositiveRate)) / (Math.log(2) * Math.log(2))
    // )
    // this.hashFunctionCount = Math.ceil(
    //   (this.bitArraySize / expectedItems) * Math.log(2)
    // )
    
    // this.bitArray = new Array(this.bitArraySize).fill(false)
    // this.itemCount = 0
  }

  /**
   * 哈希函数1
   * @param {string} str - 输入字符串
   * @returns {number} - 哈希值
   */
  hash1(str) {
    // TODO: 实现第一个哈希函数
    // 使用简单的字符串哈希算法
  }

  /**
   * 哈希函数2
   * @param {string} str - 输入字符串
   * @returns {number} - 哈希值
   */
  hash2(str) {
    // TODO: 实现第二个哈希函数
    // 使用不同的哈希算法
  }

  /**
   * 哈希函数3
   * @param {string} str - 输入字符串
   * @returns {number} - 哈希值
   */
  hash3(str) {
    // TODO: 实现第三个哈希函数
    // 使用另一种哈希算法
  }

  /**
   * 哈希函数4
   * @param {string} str - 输入字符串
   * @returns {number} - 哈希值
   */
  hash4(str) {
    // TODO: 实现第四个哈希函数
    // 使用第四种哈希算法
  }

  /**
   * 哈希函数5
   * @param {string} str - 输入字符串
   * @returns {number} - 哈希值
   */
  hash5(str) {
    // TODO: 实现第五个哈希函数
    // 使用第五种哈希算法
  }

  /**
   * 获取哈希函数数组
   * @returns {Function[]} - 哈希函数数组
   */
  getHashFunctions() {
    // TODO: 返回需要的哈希函数数组
  }

  /**
   * 添加元素到布隆过滤器
   * @param {string} item - 要添加的元素
   */
  add(item) {
    // TODO: 实现添加逻辑
    // 1. 获取所有哈希函数
    // 2. 对元素进行哈希计算
    // 3. 将对应的位设置为true
    // 4. 增加元素计数
  }

  /**
   * 检查元素是否可能在集合中
   * @param {string} item - 要检查的元素
   * @returns {boolean} - 是否可能存在
   */
  contains(item) {
    // TODO: 实现检查逻辑
    // 1. 获取所有哈希函数
    // 2. 对元素进行哈希计算
    // 3. 检查所有对应的位是否都为true
    // 4. 如果都为true，返回true；否则返回false
  }

  /**
   * 获取已添加的元素数量
   * @returns {number} - 元素数量
   */
  getItemCount() {
    // TODO: 返回已添加的元素数量
  }

  /**
   * 获取位数组大小
   * @returns {number} - 位数组大小
   */
  getBitArraySize() {
    // TODO: 返回位数组大小
  }

  /**
   * 获取哈希函数数量
   * @returns {number} - 哈希函数数量
   */
  getHashFunctionCount() {
    // TODO: 返回哈希函数数量
  }

  /**
   * 获取当前假阳性率
   * @returns {number} - 假阳性率
   */
  getFalsePositiveRate() {
    // TODO: 计算并返回当前假阳性率
    // 公式: (1 - e^(-k*n/m))^k
    // k: 哈希函数数量, n: 元素数量, m: 位数组大小
  }

  /**
   * 清空布隆过滤器
   */
  clear() {
    // TODO: 清空所有位并重置计数
  }

  /**
   * 获取位数组密度
   * @returns {number} - 位数组密度
   */
  getBitArrayDensity() {
    // TODO: 计算并返回位数组密度
    // 密度 = 设置为true的位数 / 总位数
  }

  /**
   * 估算当前实际存储的元素数量
   * @returns {number} - 估算的元素数量
   */
  estimateItemCount() {
    // TODO: 根据位数组密度估算元素数量
    // 使用公式: -m * ln(1 - p) / k
    // m: 位数组大小, p: 密度, k: 哈希函数数量
  }
}

module.exports = BloomFilter